package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0051.N%E7%9A%87%E5%90%8E.md
 * <p>
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：[["Q"]]
 */
public class SCode51 {


    public static void main(String[] args) {
        List<List<String>> ret = solveNQueens(4);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<String>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    char[][] chess;

    public static List<List<String>> solveNQueens(int n) {
        char[][] chess = new char[n][n];
        for (char[] c : chess) {
            Arrays.fill(c, '.');
        }
        backtracking(n, 0, chess);
        return ret;
    }

    /**
     * TODO 没理解
     */

    /**
     * 首先来看一下皇后们的约束条件：
     * <p>
     * 不能同行
     * 不能同列
     * 不能同斜线
     * 确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
     */
    public static void backtracking(int n, int row, char[][] chess) {
        if (n == row) {
            ret.add(Array2List(chess));
            return;
        }

        /**
         * 横向是列
         * 纵向是行
         */
        for (int col = 0; col < n; col++) {
            //先判断是否符合几个约束条件，符合再往下递归
            if (isValid(row, col, n, chess)) {
                chess[row][col] = 'Q';
                backtracking(n, row + 1, chess);
                chess[row][col] = '.';
            }
        }
    }

    public static boolean isValid(int row, int col, int n, char[][] chess) {
        //不能同列
        for (int i = 0; i < row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }
        //检查45度角是否有皇后,不能同斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        //检查135度角是否有皇后,不能同斜线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }

        return true;

    }

    public static List Array2List(char[][] chess) {
        List<String> ret = new ArrayList<>();
        for (char[] c : chess) {
            ret.add(String.copyValueOf(c));
        }
        return ret;
    }


}
